package list;

public class HuanXingLianBiao {
    public static void main(String[] args) {
        Node head = new Node(8);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(1);
        head.next.next.next.next = new Node(9);

        head.next.next.next.next.next = head.next; //形成环，从末尾节点应用前面的节点

        boolean b = hasCircle(head);
        System.out.println("是否有环："+b);
    }


    /*
    思路： 用快慢指针，快指针每次移动两步，慢指针每次移动一步，
          如果移动过程中，快慢指针重合，就表示有环；
          如果快指针都移动结束，就表示没有环。

    1. 变量fast, slow，都引用头部节点
    2. 进入循环，执行条件：fast!=null，并且fast.next!=null
    3. fast和slow一次次向后移动
    4. fast和slow如果引用同一个节点，直接返回true
    5. 循环结束，没有环，返回false
     */
    private static boolean hasCircle(Node head) {
        Node fast = head; //快指针
        Node slow = head; //慢指针
        //fast在中间位置，还可以继续向后移动
        while (fast != null && fast.next != null) {
            fast = fast.next.next; //fast走两步
            slow = slow.next;      //slow走一步
            if (fast == slow) {    //fast有没有绕回来，和slow重合
                return true;       //重合就是有环
            }
        }
        return false; //fast不能再继续向后移动时，就是没有环
    }


    static class Node{
        int value;
        Node prev;
        Node next;
        Node(int value){
            this.value=value;
        }
    }
}
